package com.example.leetcode.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * 你可以认为每种硬币的数量是无限的。
 *
 *
 *
 * 示例 1：
 *
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 * 示例 2：
 *
 * 输入：coins = [2], amount = 3
 * 输出：-1
 * 示例 3：
 *
 * 输入：coins = [1], amount = 0
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= coins.length <= 12
 * 1 <= coins[i] <= 231 - 1
 * 0 <= amount <= 104
 */
public class leetcode322 {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;

        Solution solution = new Solution();
        System.out.println(solution.coinChange(coins, amount));
    }

    static class Solution {
        public int coinChange(int[] coins, int amount) {
            if (amount == 0) return 0;

            Queue<Integer> queue = new LinkedList<>();
            boolean[] visited = new boolean[amount + 1];

            queue.offer(0); // 初始金额为0
            visited[0] = true;

            int level = 0; // 层数 = 使用的硬币数

            while (!queue.isEmpty()) {
                level++; // 进入下一层（多用了一枚硬币）
                int size = queue.size();

                for (int i = 0; i < size; i++) {
                    int curr = queue.poll();

                    for (int coin : coins) {
                        int next = curr + coin;

                        if (next == amount) return level; // 找到目标
                        if (next > amount || visited[next]) continue;

                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }

            return -1; // 无法凑出金额
        }
    }


//    static class Solution {
//        private int minCount = Integer.MAX_VALUE;
//
//        public int coinChange(int[] coins, int amount) {
//            Arrays.sort(coins);
//            // 从大到小尝试，有利于更快凑出目标金额
//            reverse(coins);
//            dfs(coins, 0, amount, 0);
//            return minCount == Integer.MAX_VALUE ? -1 : minCount;
//        }
//
//        // 回溯搜索
//        private void dfs(int[] coins, int index, int amount, int count) {
//            if (amount == 0) {
//                minCount = Math.min(minCount, count);
//                return;
//            }
//            if (index == coins.length) return;
//
//            int coin = coins[index];
//            // 最多能使用 k 枚当前硬币
//            int maxK = amount / coin;
//            for (int k = maxK; k >= 0; k--) {
//                int newCount = count + k;
//                // 剪枝：如果当前路径硬币数已不优，则不继续
//                if (newCount >= minCount) break;
//
//                int newAmount = amount - k * coin;
//                dfs(coins, index + 1, newAmount, newCount);
//            }
//        }
//
//        // 数组反转
//        private void reverse(int[] arr) {
//            int i = 0, j = arr.length - 1;
//            while (i < j) {
//                int t = arr[i];
//                arr[i++] = arr[j];
//                arr[j--] = t;
//            }
//        }
//    }


//    static class Solution {
//        public int coinChange(int[] coins, int amount) {
//            int[] dp = new int[amount + 1];
//            Arrays.fill(dp, amount + 1);
//            dp[0] = 0;
//
//            for (int i = 1; i <= amount; i++) {
//                for (int coin : coins) {
//                    if (coin <= i) {
//                        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
//                    }
//                }
//            }
//
//            return dp[amount] == amount + 1 ? -1 : dp[amount];
//        }
//    }
}
